#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
#include <string>
using namespace std;
class Solution {
public:
    int difference(const string& s1, const string& s2) {
        int count = 0;
        for (int i = 0; i < s1.size(); i++) {
            if (s1[i] != s2[i])
                ++count;
        }
        return count;
    }
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        if (startGene == endGene)
            return 0;
        int n = bank.size();
        vector<bool> sta(n, false);
        queue<string> q;
        q.push(startGene);
        int count = 0;
        while (!q.empty()) {
            int cnt = q.size();
            ++count;
            while (cnt--) {
                string s = q.front();
                q.pop();
                for (int i = 0; i < n; i++) {
                    if (sta[i] == false && difference(s, bank[i]) == 1 &&
                        bank[i] != startGene) {
                        // cout << bank[i] << endl;
                        // for (auto a : sta)
                        //     cout << a << " ";
                        //cout << endl;
                        if (bank[i] == endGene)
                            return count;
                        q.push(bank[i]);
                        sta[i] = true;
                    }
                }
            }
        }
        return -1;
    }
};